def find_root_node(data: list) -> list:
    """
    查找根节点
    :param data:原始数据
    :return:根节点
    """
    # root_node = filter(lambda x: x["p_id"] is None, data)

    root_node = list()
    for node in data:
        # 假定p_id是None就是根节点
        # 例如有些数据库设计会直接把根节点标识出来。
        if node["p_id"] is None:
            root_node.append(node)
    return root_node


def find_common_node(data: list) -> dict:
    """
    寻找共同的父节点
    :param data: 原始数据
    :return: 共同的父节点字典
    """
    common_node = dict()

    for node in data:
        p_id = node.get("p_id")
        # 排除根节点情况
        if p_id is not None:
            # 如果父节点ID不在字典中则添加到字典中
            if p_id not in common_node:
                common_node[p_id] = list()
            common_node[p_id].append(node)
    return common_node


def build_tree(root_node: list, common_node: dict) -> list:
    """
    生成目录树
    :param root_node: 根节点列表
    :param common_node: 共同父节点字典
    :return:
    """
    tree = list()
    for root in root_node:
        # 生成字典
        base = dict(title=root["title"], id=root["id"], children=list())
        # 遍历查询子节点
        find_children(base["id"], base["children"], common_node)
        # 添加到列表
        tree.append(base)
    return tree


def find_children(p_id: int, children_node: list, common_node: dict):
    """
    查找子节点
    :param p_id:父级ID
    :param children_node: 父级孩子节点
    :param common_node: 共同父节点字典
    :return:
    """
    # 获取共同父节点字典的子节点数据
    children_list = common_node.get(p_id, [])
    for item in children_list:
        # 生成字典
        base = dict(title=item["title"], id=item["id"], children=list())
        # 遍历查询子节点
        find_children(item["id"], base["children"], common_node)
        # 添加到列表
        children_node.append(base)

